#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> vv;

bool find(vector<int> &v, int num)
{
    for(int j = 0; j < v.size(); j++)
        if(v[j] == num)
            return true;
    return false;
}

void recursion(vector<int> &nums, vector<int> &v)
{
    if(v.size() == nums.size())
    {
        vv.push_back(v);
        return;
    }
    for(int i = 0; i < nums.size(); i++)
    {
        if(find(v, nums[i]))
            continue;
        vector<int> newvector(v);
        newvector.push_back(nums[i]);
        recursion(nums, newvector);
    }
}

vector<vector<int>> permute(vector<int> &nums)
{
    // write your code here
    vv.clear();
    vector<int> v;
    recursion(nums, v);
    return vv;
}

void printVV(vector<vector<int>> &vv)
{
    for(int i = 0; i < vv.size(); i++)
    {
        for(int j = 0; j < vv[i].size(); j++)
            printf("%d\t", vv[i][j]);
        printf("\n");
    }
}
int main()
{
    vector<int> nums = {1,2,3,4,5};
    permute(nums);
    printVV(vv);
    return 0;
}

/**
全排列

给定一个数字列表，返回其所有可能的排列。
注意事项

你可以假设没有重复数字。

样例

给出一个列表[1,2,3]，其全排列为：

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

*/
